package jm.data.structure.hash;

/**
 * @Description
 * @date 2022/4/28 14:47
 */
public class LinkedHashMap<K,V> extends HashMap<K,V>{

    // 头节点和尾节点
    private LinkedNode<K,V> first;
    private LinkedNode<K,V> last;

    @Override
    public void clear() {
        super.clear();
        first = null;
        last = null;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        if (visitor == null){
            return;
        }
        LinkedNode<K, V> node = this.first;
        while (node != null){
            if (visitor.visit(node.key,node.value)){
                return;
            }
            node = node.next;
        }
    }

    @Override
    protected void afterRemoveLinked(Node<K,V> willNode, Node<K, V> node) {
        LinkedNode<K, V> linkedWillNode = (LinkedNode<K, V>) willNode;
        LinkedNode<K, V> linkedNode = (LinkedNode<K, V>) node;

        if (linkedWillNode != linkedNode) {
            // 交换linkedWillNode和linkedRemovedNode在链表中的位置
            // 交换prev
            LinkedNode<K, V> tmp = linkedWillNode.prev;
            linkedWillNode.prev = linkedNode.prev;
            linkedNode.prev = tmp;
            if (linkedWillNode.prev == null) {
                first = linkedWillNode;
            } else {
                linkedWillNode.prev.next = linkedWillNode;
            }
            if (linkedNode.prev == null) {
                first = linkedNode;
            } else {
                linkedNode.prev.next = linkedNode;
            }

            // 交换next
            tmp = linkedWillNode.next;
            linkedWillNode.next = linkedNode.next;
            linkedNode.next = tmp;
            if (linkedWillNode.next == null) {
                last = linkedWillNode;
            } else {
                linkedWillNode.next.prev = linkedWillNode;
            }
            if (linkedNode.next == null) {
                last = linkedNode;
            } else {
                linkedNode.next.prev = linkedNode;
            }
        }

        LinkedNode<K, V> prev = linkedNode.prev;
        LinkedNode<K, V> next = linkedNode.next;
        if (prev == null){
            first = next;
        }else {
            prev.next = next;
        }
        if (next == null){
            last = prev;
        }else {
            next.prev = prev;
        }
    }


    @Override
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        LinkedNode<K, V> node = new LinkedNode<>(key, value, parent);
        if (first == null){  // 头节点为空时
            first = last = node;
        }else { // 新元素作为最后一个元素
            last.next = node;
            node.prev = last;
            last = node;
        }
        return node;
    }

    private static class LinkedNode<K,V> extends Node<K,V>{
        LinkedNode<K,V> prev;
        LinkedNode<K,V> next;
        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}
